package com.itheima.datastructure.linkedlist;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * @author tantao
 * @version 1.0
 * @description: 单向链表(没有哑元节点) - 泛型版本
 * @date 2025/8/6 14:36
 */
public class SinglyLinkedList01<E> implements Iterable<E> {

    private Node head = null; //头节点

    //构造方法
    public SinglyLinkedList01() {
    }

    /**
     * 添加元素到链表头部
     *
     * @param value value
     */
    public void addFirst(E value) {
//        if (null == head) {
//            //链表为空,创建一个头节点
//            head = new Node(value, null);
//        } else {
//            //链表非空,则将头节点指向新的头节点
//            head = new Node(value, head);
//        }

        //---简化---
        head = new Node(value, head);
    }

    /**
     * 添加元素到链表尾部
     *
     * @param value value
     */
    public void addLast(E value) {
        //找到最后一个节点
        Node last = findLast();
        if (last == null) { //如果链表为空
            addFirst(value);
            return;
        }
        //找到最后的节点
        last.next = new Node(value, null);
    }

    /**
     * 找到最后一个节点
     *
     * @return Node
     */
    private Node findLast() {
        //如果链表为空，则返回null
        if (null == head) {
            return null;
        }

        //如果链表非空，则返回最后一个节点
        Node cur = head;
        while (cur.next != null) {
            //移动指针
            cur = cur.next;
        }
        return cur;

    }

    /**
     * 遍历1
     *
     * @param consumer consumer
     */
    public void loop1(Consumer<E> consumer) {
        Node ptr = head;
        while (ptr != null) {
            consumer.accept(ptr.value);
            //移动指针
            ptr = ptr.next;
        }
    }

    /**
     * 遍历2
     *
     * @param consumer consumer
     */
    public void loop2(Consumer<E> consumer) {
        for (Node ptr = head; ptr != null; ptr = ptr.next) {
            consumer.accept(ptr.value);
        }
    }

    public void loop3(Consumer<E> before, Consumer<E> after) {
        recursion(head, before, after);
    }

    private void recursion(Node curr, Consumer<E> before, Consumer<E> after) {
        if (curr == null) {
            return;
        }
        before.accept(curr.value);
        recursion(curr.next, before, after);
        after.accept(curr.value);
    }


    /**
     * 获取指定索引的元素
     *
     * @param index index
     * @return E
     */
    public E get(int index) {
        Node ptr = findNode(index);
        if (ptr == null) {
            throw illegalIndex(index);
        }
        return ptr.value;
    }


    //找到指定索引的节点
    private Node findNode(int index) {
        //--- 使用while循环 ----
//        int i = 0;
//        Node cur = head;
//        while (cur != null) {
//            if (i == index) {
//                return cur;
//            }
//            cur = cur.next;
//            i++;
//        }
//        return cur;

        //--- 使用for循环 ----

        int idx = 0;
        for (Node ptr = head; ptr != null; ptr = ptr.next, idx++) {
            if (idx == index) {
                return ptr;
            }
        }
        return null;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }


    private void checkIndex(int index) {
        if (index < 0) {
            throw illegalIndex(index);
        }
    }

    /**
     * 插入元素
     *
     * @param index index
     * @param value v
     */
    public void insert(int index, E value) {
        checkIndex(index);
        if (index == 0) {
            addFirst(value);
            return;
        }
        //找到上一个节点
        Node prev = findNode(index - 1);
        if (null == prev) { // 找不到
            throw illegalIndex(index);
        }
        // --- 新建的节点 要插在 prev和next之间

        //找到下一个节点
        Node next = prev.next;
        //新节点的next 就是下一个节点
        Node c = new Node(value, next);
        //上一个节点的next 指向新节点
        prev.next = c;
    }

    public void removeFirst() {
        if (head == null) {
            throw new IllegalArgumentException("链表为空");
        }
        //获取下一个节点
        Node next = head.next;

        //将下一个节点赋给head
        head = next;
    }

    public void removeLast() {
        if (head == null) {
            throw new IllegalArgumentException("链表为空");
        }
        // 如果只有一个节点，直接将头节点设为null
        if (head.next == null) {
            head = null;
            return;
        }

        // 找到倒数第二个节点
        Node cur = head;
        //当前节点的下一个的下一个为空，则说明当前的是倒数第二个
        while (cur.next.next != null) {
            // 移动指针
            cur = cur.next;
        }

        // 删除倒数第二个的下一个，则删除的是倒数第一个
        cur.next = null;
    }

    public void remove(int index) {
        if (index <= 0) {
            removeFirst();
            return;
        }
        //找到上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        //当前要删除的节点
        Node curr = prev.next;
        if (curr == null) {
            throw illegalIndex(index);
        }

        //下一个节点
        Node next = curr.next;

        //上一个节点的next指向下一个节点
        prev.next = next;
    }

    /**
     * 遍历3
     *
     * @return iterator
     */
    @Override
    public Iterator<E> iterator() {
        //匿名内部类 -> 带名字内部类
        return new NodeIterator();
    }

    //节点类-对外不可见 {内部类使用了外部类的成员变量时，不能加static}
    private class Node {
        public E value;  // 节点存储的数据
        public Node next; // 指向下一个节点

        public Node(E value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    //{内部类使用了外部类的成员变量时，不能加static}
    private class NodeIterator implements Iterator<E> {
        Node crr = head;

        @Override
        public boolean hasNext() { //是否有下一个值
            return crr != null;
        }

        @Override
        public E next() {
            E value = crr.value; //返回当前值
            crr = crr.next; //并指向下一个元素
            return value;
        }
    }
}
